package day_2022_4_to_7.nowcoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * 最小的K个数
 * @author haomin
 * @date 2022/05/05 20:21
 **/
public class GetLeastNumbersTopK_24f {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        // 判断传入的参数是否合法
        if(input.length == 0 || k <= 0 || k > input.length){
            return result;
        }

        //1. 先创建一个容量为k的大根堆queue
        // k 为容量；Collections.reverseOrder() 指按大根堆排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());

        // 2. 遍历数组，使所有元素进行入队操作
        for (int i = 0; i < input.length; i++) {
            if(i < k){
                // 2.1 先将前k个元素先入队
                queue.add(input[i]);
            }else {
                // 2.2 入队k 后面的元素
                if(queue.peek() > input[i]){
                    // 如果根节点值>当前元素，就将根节点出队，当前元素入队
                    queue.poll();
                    queue.add(input[i]);
                }
            }
        }

        // 3. 当所有元素入队结束后，大根堆queue中存储的就是前k个最小的数
        // 传入到result中
        for (int i = 0; i < k; i++) {
            result.add(queue.poll());
        }
        return result;
    }
}